#include <iostream>
#include <vector>
using namespace std;

class segment_tree {
	long val = 0;
	long LOWEST = -1;
	long MAXN = 1000001;

	vector<long long> sum;
	vector<long> imax;
	vector<long> mcnt;
	vector<long> isem;

	void lazy(int i, int v)
	{
		if (v < imax[i]) {
			sum[i] -= (imax[i] - v) * mcnt[i];
			imax[i] = v;
		}
	}

	void up(int i)
	{
		int l = i << 1;
		int r = i << 1 | 1;
		sum[i] = sum[l] + sum[r];
		imax[i] = max(imax[l], imax[r]);

		if (imax[l] == imax[r]) {
			mcnt[i] = mcnt[l] + mcnt[r];
			isem[i] = max(isem[l], isem[r]);
		} else if (imax[l] > imax[r]) {
			mcnt[i] = mcnt[l];
			isem[i] = max(isem[l], imax[r]);
		} else {
			mcnt[i] = mcnt[r];
			isem[i] = max(isem[r], imax[l]);
		}
	}

	void down(int i)
	{
		lazy(i << 1, imax[i]);
		lazy(i << 1 | 1, imax[i]);
	}

    public:
	segment_tree() : sum(MAXN << 2, 0), imax(MAXN << 2, 0), isem(MAXN << 2, 0), mcnt(MAXN << 2, 0)
	{
	}

	void build(int l, int r, int i)
	{
		if (l == r) {
			cin >> val;
			sum[i] = imax[i] = val;
			mcnt[i] = 1;
			isem[i] = LOWEST;
		} else {
			int mid = (l + r) >> 1;
			build(l, mid, i << 1);
			build(mid + 1, r, i << 1 | 1);
			up(i);
		}
	}

	void set_min(int jobl, int jobr, long v, int l, int r, int i)
	{
		if (imax[i] <= v) {
			return;
		}
		if (jobl <= l && r <= jobr && isem[i] < v) {
			lazy(i, v);
		} else {
			int mid = (l + r) >> 1;
			down(i);
			if (jobl <= mid) {
				set_min(jobl, jobr, v, l, mid, i << 1);
			}
			if (mid < jobr) {
				set_min(jobl, jobr, v, mid + 1, r, i << 1 | 1);
			}
			up(i);
		}
	}

	long query_max(int jobl, int jobr, int l, int r, int i)
	{
		if (jobl <= l && r <= jobr) {
			return imax[i];
		}
		down(i);
		int mid = (l + r) >> 1;
		long ans = -1;
		if (jobl <= mid) {
			ans = max(ans, query_max(jobl, jobr, l, mid, i << 1));
		}
		if (mid < jobr) {
			ans = max(ans, query_max(jobl, jobr, mid + 1, r, i << 1 | 1));
		}
		return ans;
	}

	long long query_sum(int jobl, int jobr, int l, int r, int i)
	{
		if (jobl <= l && r <= jobr) {
			return sum[i];
		}
		down(i);
		int mid = (l + r) >> 1;
		long long ans = 0;
		if (jobl <= mid) {
			ans += query_sum(jobl, jobr, l, mid, i << 1);
		}
		if (mid < jobr) {
			ans += query_sum(jobl, jobr, mid + 1, r, i << 1 | 1);
		}
		return ans;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	segment_tree sgt;
	while (t--) {
		int n, m;
		cin >> n >> m;

		sgt.build(1, n, 1);
		for (int i = 0, op, x, y, v; i < m; i++) {
			cin >> op >> x >> y;
			if (op == 0) {
				cin >> v;
				sgt.set_min(x, y, v, 1, n, 1);
			}

			if (op == 1) {
				cout << sgt.query_max(x, y, 1, n, 1) << '\n';
			}

			if (op == 2) {
				cout << sgt.query_sum(x, y, 1, n, 1) << '\n';
			}
		}
	}
	return 0;
}